home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / general / plotting / imagetoo / imagetl1.lha / Imagetool / HDF / dfimcomp.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-09-20  |  35.6 KB  |  1,256 lines
  1. /*****************************************************************************
  2. * 
  3. *              NCSA HDF version 3.10
  4. *                July 1, 1990
  5. *
  6. * NCSA HDF Version 3.10 source code and documentation are in the public
  7. * domain.  Specifically, we give to the public domain all rights for future
  8. * licensing of the source code, all resale rights, and all publishing rights.
  9. * 
  10. * We ask, but do not require, that the following message be included in all
  11. * derived works:
  12. * 
  13. * Portions developed at the National Center for Supercomputing Applications at
  14. * the University of Illinois at Urbana-Champaign.
  15. * 
  16. * THE UNIVERSITY OF ILLINOIS GIVES NO WARRANTY, EXPRESSED OR IMPLIED, FOR THE
  17. * SOFTWARE AND/OR DOCUMENTATION PROVIDED, INCLUDING, WITHOUT LIMITATION,
  18. * WARRANTY OF MERCHANTABILITY AND WARRANTY OF FITNESS FOR A PARTICULAR PURPOSE
  19. * 
  20. *****************************************************************************/
  21.  
  22. #ifdef RCSID
  23. static char RcsId[] = "@(#)$Revision: 3.4 $";
  24. #endif
  25. /*
  26. $Header: /pita/work/HDF/dev/RCS/src/dfimcomp.c,v 3.4 90/07/02 10:12:07 clow beta $
  27.  
  28. $Log:    dfimcomp.c,v $
  29.  * Revision 3.4  90/07/02  10:12:07  clow
  30.  * some cosmetic modifications
  31.  * 
  32. */
  33. /************************************************************************/
  34. /*  Module Name : imcomp                        */
  35. /*  Exports     : DFCimcomp(), DFCunimcomp()                */
  36. /*  Purpose     : Compresses color images               */
  37. /*  Author  : Eng-Kiat Koh                      */
  38. /*  Date    : June 30th, 1988                   */
  39. /*  Functions   : DFCimcomp(), compress(), init_global(), cnt_color()   */
  40. /*        set_palette(), fillin_color(), map(), nearest_color() */
  41. /*        DFCunimcomp(), sqr()                                  */
  42. /************************************************************************/
  43.  
  44.  
  45. #include "df.h"
  46.  
  47. #define PALSIZE 256
  48. #define BIT8 0
  49. #define BIT24 1
  50.  
  51. #ifndef MAC
  52. #define MAXCOLOR 32768
  53. #else /*MAC*/
  54. #define MAXCOLOR 768
  55. #endif /*MAC*/
  56.  
  57. #ifndef NULL
  58. #   define NULL 0
  59. #endif
  60.  
  61. #define RED 0
  62. #define GREEN 1
  63. #define BLUE 2
  64. #define EPSILON 0.5
  65. #define LO 1
  66. #define HI 0
  67.  
  68. struct rgb
  69. {
  70.   unsigned char c[3];
  71. };
  72.  
  73. struct box
  74. {
  75.   float bnd[3][2];
  76.   int *pts;
  77.   int nmbr_pts;
  78.   int nmbr_distinct;
  79.   struct box *left;
  80.   struct box *right;
  81. };
  82.  
  83.  
  84. unsigned char *new_pal;          /* pointer to new palette           */
  85.  
  86.  
  87. static int *hist = (int *)NULL;    /* histogram for distinct colors    */
  88. static struct box *frontier = (struct box *)NULL; /* pointer to the */
  89.                           /* list of boxes */
  90. static struct rgb *distinct_pt = (struct rgb *)NULL; /* contains all */
  91.                              /* distinct rgb points */
  92.  
  93. static void sel_palette();
  94. static void compress();
  95. static void init_global();
  96. static int cnt_color();
  97. static void set_palette();
  98. static void fillin_color();
  99. static int indx();
  100. static void map();
  101. static int nearest_color();
  102. static long int sqr();
  103. static void init();
  104. static int partition();
  105. static struct box *find_box();
  106. static void split_box();
  107. static void assign_color();
  108. static int select_dim();
  109. static float find_med();
  110. static void classify();
  111. static int next_pt();
  112.  
  113. /* extern char *calloc(); */
  114.  
  115. static struct rgb *color_pt = (struct rgb *)NULL; /*contains the hi-lo */
  116.                           /*colors for each block*/
  117. static unsigned char *image;    /* contains the compressed image            */
  118. static int trans[MAXCOLOR];     /* color translation table                  */
  119.  
  120. /************************************************************************/
  121. /*  Function    : DFCimcomp                                             */
  122. /*  Purpose : Performs Imcomp Compression                           */
  123. /*  Parameters  :                                                       */
  124. /*    xdim, ydim - dimensions of image                                  */
  125. /*                 IT IS ASSUMED THAT THE DIMENSIONS ARE A MULTIPLE OF 4*/
  126. /*    in, out    - input image array and output image buffer size of in */
  127. /*                 is xdim*ydim bytes for 8 bit per pixel mode. It is 3 */
  128. /*                 times that for 24 bits per pixel mode. The output    */
  129. /*                 buffer is always (xdim*ydim)/4.                      */
  130. /*    in_pal     - input palette. Consist of rgb triples unlike seq-type*/
  131. /*                 palette. This is a NULL pointer if operating at the  */
  132. /*                 24 bit per pixel mode.                               */
  133. /*    out_pal    - output palette. Consist of PALSIZE color entries.    */
  134. /*                 each entry is an rgb triple.                         */
  135. /*    mode       - Either BIT8 or BIT24                                 */
  136. /*  Returns     : none                          */
  137. /*  Called by   : External routines                                     */
  138. /*  Calls       : init_global(), compress(), cnt_color(), set_palette(),*/
  139. /*        sel_palette(), map()                                  */
  140. /************************************************************************/
  141.  
  142. void DFCimcomp(xdim, ydim, in, out, in_pal, out_pal, mode)
  143. int32 xdim, ydim;
  144. int mode;
  145. char in[], out[], in_pal[], out_pal[];
  146. {
  147.   unsigned char raster[48];
  148.   int blocks, nmbr, i, j, k, l, x, y;
  149.   void init_global();
  150.   void compress();
  151.   int cnt_color();
  152.   void set_palette();
  153.   void sel_palette();
  154.   void map();
  155.   void fillin_color();
  156.  
  157.   init_global(xdim, ydim, out, out_pal);
  158.  
  159.   /* compress pixel blocks */
  160.   blocks = 0;
  161.   for (i=0; i<(ydim/4); i++)
  162.     for (j=0; j<(xdim/4); j++)
  163.     {
  164.       switch (mode)
  165.       {
  166.         case BIT8 : /* 8 bit per pixel format */
  167.             k = 0;
  168.             for (y=(i*4); y<(i*4+4); y++)
  169.               for (x=(j*4); x<(j*4+4); x++)         
  170.               {
  171.             l = y*xdim + x;
  172.             raster[k++] = (unsigned char) in_pal[3 * (unsigned char)in[l]];
  173.             raster[k++] = (unsigned char) in_pal[3 * (unsigned char)in[l] + 1];
  174.             raster[k++] = (unsigned char) in_pal[3 * (unsigned char)in[l] + 2];
  175.               } /* end of for x */
  176.             compress(raster,blocks);
  177.             break;
  178.  
  179.       case BIT24: /* 24 bit per pixel format */
  180.             k = 0;
  181.             for (y=(i*4); y<(i*4+4); y++)
  182.               for (x=(j*4); x<(j*4+4); x++)         
  183.               {
  184.             l = 3 *(y*xdim + x);
  185.             raster[k++] = (unsigned char) in[l];
  186.             raster[k++] = (unsigned char) in[l+1];
  187.             raster[k++] = (unsigned char) in[l+2];
  188.               } /* end of for x */
  189.             compress(raster,blocks);
  190.             break;
  191.     
  192.     default   : /* unsupported format */
  193.             printf("Error : Unsupported Format \n");
  194.             exit(1);
  195.             break;
  196.       } /* end of switch */
  197.       
  198.       blocks++;
  199.     } /* end of for j */
  200.  
  201.   /* set palette */
  202.   nmbr = cnt_color(blocks);
  203. /*
  204.   printf("Number of colors %d \n", nmbr);
  205. */
  206.   if (nmbr <= PALSIZE)
  207.     set_palette(blocks);
  208.   else
  209.   {
  210.     sel_palette(blocks,nmbr,color_pt);
  211.     map(blocks);
  212.   }
  213.  
  214.   fillin_color(blocks);
  215.  
  216. } /* end of DFCimcomp */
  217.  
  218.  
  219.  
  220.  
  221.  
  222.  
  223. /************************************************************************/
  224. /*  Function    : compress                                  */
  225. /*  Purpose : Given a block of 16 pixels, sets up a 16 bit bitmap   */
  226. /*                and assigns a lo and hi color for the block. For block*/
  227. /*                i, hi color is stored in color_pt[2i] and lo in       */
  228. /*                color_pt[2i+1]. Each color is then reduced to 15 bits */
  229. /*                by truncating the lower order 3 bits of each component*/
  230. /*  Parameter   :                           */
  231. /*    raster     - contains the 16 pixels of a block. Each pixel is 3   */
  232. /*         bytes, 1 byte for each color component               */
  233. /*    block  - pixel block number                                   */
  234. /*  Returns     : none                                                  */
  235. /*  Called by   : DFCimcomp()                       */
  236. /*  Calls       : none                          */
  237. /************************************************************************/
  238.  
  239. static void compress(raster, block)
  240. unsigned char raster[];
  241. int block;
  242. {
  243.   float y[16], y_av;
  244.   int i, j, k, l, bit;
  245.   int high, hi, lo;
  246.   int c_hi[3], c_lo[3];
  247.  
  248.   /* calculate luminance */
  249.   y_av = 0.0;
  250.   for (i=0; i<16; i++)
  251.   {
  252.     j = 3*i;
  253.     y[i] = 0.3*(float)raster[j] + 0.59*(float)raster[j+1] + 
  254.            0.11*(float)raster[j+2];
  255. /*    printf("compress: y[%d] is %f\n",i,y[i]);*/
  256.     y_av = y_av + y[i];
  257.   }
  258.   y_av = y_av / 16.0;
  259. /*  printf("y_av is %f\n",y_av); */
  260.  
  261.   /* initialize c_hi and c_lo */
  262.   for (i=RED; i<=BLUE; i++)
  263.   {
  264.     c_hi[i] = 0;
  265.     c_lo[i] = 0;
  266.   }
  267.  
  268.   /* build bit map */
  269.   k = 4 * block;
  270.   high = 0;
  271.   hi = 2 * block;
  272.   lo = hi + 1;
  273.   for (i=0; i<2; i++)
  274.   {
  275.     bit = 128;
  276.     for (j = (i*8); j<(i*8+8); j++)
  277.     {
  278.       if (y[j] > y_av)
  279.       {
  280.     image[k] = image[k] | bit;
  281.     high++;
  282.         for (l=RED; l<= BLUE; l++)
  283.       c_hi[l] = c_hi[l] + (int)raster[3*j+l];
  284.       }
  285.       else
  286.       {
  287.     for (l=RED; l<=BLUE; l++)
  288.           c_lo[l] = c_lo[l] + (int)raster[3*j+l];
  289.       } /* end of if */
  290.  
  291.       bit = bit >> 1;
  292.     } /* end of for j */
  293.    
  294.     k++;
  295.   } /* end of for i */
  296.  
  297.   /* calculate hi lo color */
  298.   for (i=RED; i<=BLUE; i++)
  299.   {
  300.     if (high != 0)
  301.       color_pt[hi].c[i] = (int)((float)c_hi[i] / (float)high);
  302.     if (high != 16)
  303.       color_pt[lo].c[i] = (int)((float)c_lo[i] / (float)(16 - high));
  304.     color_pt[hi].c[i] = color_pt[hi].c[i] >> 3;
  305.     color_pt[lo].c[i] = color_pt[lo].c[i] >> 3;
  306.  
  307.   }
  308. } /* end of compress */
  309.  
  310.  
  311.  
  312.  
  313.  
  314.  
  315. /************************************************************************/
  316. /*  Function    : init_global                       */
  317. /*  Purpose : Allocates memory for global variables                 */
  318. /*  Parameter   :                           */
  319. /*    xdim, ydim - x and y dimension of image               */
  320. /*    out        - pointer to output buffer                             */
  321. /*    out_pal    - pointer to output palette                            */
  322. /*  Returns     : none                              */
  323. /*  Called by   : DFCimcomp()                       */
  324. /*  Calls       : none                          */
  325. /************************************************************************/
  326.  
  327. static void init_global(xdim, ydim, out, out_pal)
  328. int32 xdim, ydim;
  329. char *out, *out_pal;
  330. {
  331.   int i, j;
  332.  
  333.   /* allocate memory */
  334.   image = (unsigned char *) out;
  335.   new_pal = (unsigned char *) out_pal;
  336.   if (color_pt) DFIfreespace((char *) color_pt);
  337.   color_pt = (struct rgb *)DFIgetspace((unsigned)((xdim*ydim)/8) *
  338.                        sizeof(struct rgb));
  339.  
  340.   if (image == NULL || color_pt == NULL || new_pal == NULL)
  341.   {
  342.     printf("Error : Out of Memory\n");
  343.     exit(1);
  344.   }
  345.  
  346.   /* initialize */
  347.   for (i=0; i<(xdim*ydim/4); i++)
  348.     image[i] = 0;
  349.  
  350.   for (i=0; i<(xdim*ydim/8); i++)
  351.     for (j=RED; j<= BLUE; j++)
  352.       color_pt[i].c[j] = 0;
  353.  
  354.   for (i=0; i<MAXCOLOR; i++)
  355.     trans[i] = -1;
  356. } /* end of init_global */
  357.  
  358.  
  359.  
  360.  
  361.  
  362. /************************************************************************/
  363. /*  Function    : cnt_color                                 */
  364. /*  Purpose : Counts the number of distinct colors compressd image  */
  365. /*  Parameter   :                           */
  366. /*    blocks     - total number of pixel blocks             */
  367. /*  Returns     : Number of distinct colors                             */
  368. /*  Called by   : DFCimcomp()                                           */
  369. /*  Calls       : indx()                        */
  370. /************************************************************************/
  371.  
  372. static int cnt_color(blocks)
  373. int blocks;
  374. {
  375.   int temp[MAXCOLOR];
  376.   int i, k, count;
  377.   int indx();
  378.  
  379.   for (i=0; i<MAXCOLOR; i++)
  380.     temp[i] = -1;
  381.  
  382.   for (i=0; i<(2*blocks); i++)
  383.   {
  384.     k = indx(color_pt[i].c[RED],color_pt[i].c[GREEN],color_pt[i].c[BLUE]);
  385. /*    printf("cnt_color: k is %d\n",k); */
  386.     temp[k] = 0;
  387.   }
  388.  
  389.   count  = 0;
  390.   for (i = 0; i< MAXCOLOR; i++)
  391.     if (temp[i] == 0)
  392.       count++;
  393.  
  394.   return count;
  395. } /* end of cnt_color */
  396.  
  397.  
  398.  
  399.  
  400.  
  401. /************************************************************************/
  402. /*  Function    : set_palette                       */
  403. /*  Purpose : The number of distinct colors is less than the desired*/
  404. /*                output palette size. Therefore each distinct color can*/
  405. /*        be a palette entry. Function enters each distinct     */
  406. /*                color as a palette entry and sets up the translation  */
  407. /*                table. It also shifts each color component left 3 bits*/
  408. /*                so that each color component is again 8 bits wide     */
  409. /*  Parameter   :                           */
  410. /*    blocks     - total number of pixel blocks                         */
  411. /*  Returns     : none                          */
  412. /*  Called by   : DFCimcomp()                       */
  413. /*  Calls       : indx()                        */
  414. /************************************************************************/
  415.  
  416. static void set_palette(blocks)
  417. int blocks;
  418. {
  419.   int ent, i, k;
  420.   int indx();
  421.  
  422.   ent = 0;
  423.   for (i = 0; i<(2*blocks); i++)
  424.   {
  425.     k = indx(color_pt[i].c[RED],color_pt[i].c[GREEN],color_pt[i].c[BLUE]);
  426.     if (trans[k] == -1)
  427.     {
  428.       new_pal[3*ent] = color_pt[i].c[RED] << 3;
  429.       new_pal[3*ent+1] = color_pt[i].c[GREEN] << 3;
  430.       new_pal[3*ent+2] = color_pt[i].c[BLUE] << 3;  
  431.       trans[k] = ent;
  432.       ent++;
  433.     }
  434.   }
  435. } /* end of set_palette */
  436.  
  437.  
  438.  
  439.  
  440.  
  441. /************************************************************************/
  442. /*  Function    : fillin_color                      */
  443. /*  Purpose : For each pixel block, fills in the pointers into the  */
  444. /*                palette.                                              */
  445. /*  Parameter   :                           */
  446. /*    blocks     - total number of pixel blocks             */
  447. /*  Returns     : none                          */
  448. /*  Called by   : DFCimcomp()                       */
  449. /*  Calls       : none                          */
  450. /************************************************************************/
  451.  
  452. static void fillin_color(blocks)
  453. int blocks;
  454. {
  455.   int i, j, k;
  456.  
  457.   for (i=0; i<blocks; i++)
  458.     for (j=HI; j<=LO; j++)
  459.     {
  460.       k = indx(color_pt[2*i+j].c[RED],color_pt[2*i+j].c[GREEN],
  461.            color_pt[2*i+j].c[BLUE]);
  462.       image[i*4+2+j] = trans[k];
  463.     }
  464. } /* end of fillin_color */
  465.  
  466.  
  467.  
  468.  
  469.  
  470. /************************************************************************/
  471. /*  Function    : indx                          */
  472. /*  Purpose : Maps an rgb triple (5 bits each) to an integer array  */
  473. /*        index                         */
  474. /*  Parameter   :                           */
  475. /*    r, g, b    - color components                 */
  476. /*  Returns     : returns an array index                */
  477. /*  Called by   : set_palette(), fillin_color(), map()                  */
  478. /*  Calls       : none                          */
  479. /************************************************************************/
  480.  
  481. static int indx(r, g, b)
  482. unsigned char r, g, b;
  483. {
  484.   int temp;
  485.  
  486.   temp = 0;
  487.   temp = ((r & 0x1f) << 10) | ((g & 0x1f)  << 5) | (b & 0x1f);
  488.   return temp;
  489. } /* end of indx */
  490.  
  491.  
  492.  
  493.  
  494.  
  495.  
  496. /************************************************************************/
  497. /*  Function    : map                           */
  498. /*  Purpose : Maps a color_pt to the closest representative color   */
  499. /*        Sets up translation table             */
  500. /*  Parameter   :                           */
  501. /*    blocks     - total number of pixel blocks             */
  502. /*  Returns     : none                          */
  503. /*  Called by   : DFCimcomp()                       */
  504. /*  Calls       : nearest_color()                   */
  505. /************************************************************************/
  506.  
  507. static void map(blocks)
  508. int blocks;
  509. {
  510.   int i, k;
  511.   unsigned char r, g, b;
  512.   int indx();
  513.   int nearest_color();
  514.  
  515.   for (i=0; i<(2*blocks); i++)
  516.   {
  517.     k = indx(color_pt[i].c[RED], color_pt[i].c[GREEN], color_pt[i].c[BLUE]);
  518.  
  519.     if (trans[k] == -1)
  520.     {
  521.       r = (unsigned char) color_pt[i].c[RED]<<3;
  522.       g = (unsigned char) color_pt[i].c[GREEN]<<3;
  523.       b = (unsigned char) color_pt[i].c[BLUE]<<3;
  524.       trans[k] = nearest_color(r, g, b);
  525. /*
  526.       printf("map: %d %d %d mapped to %d %d %d\n", r, g, b, new_pal[trans[k]*3],
  527.           new_pal[trans[k]*3+1], new_pal[trans[k]*3+2]);
  528. */
  529.     }
  530.   }
  531. } /* end of map */
  532.   
  533.  
  534.  
  535.  
  536. /************************************************************************/
  537. /*  Function    : nearest_color                     */
  538. /*  Purpose : Finds the nearest palette color           */
  539. /*  Parameter   :                           */
  540. /*    r, g, b    - color component                  */
  541. /*  Returns     : Entry number of the closest color in the palette      */
  542. /*  Called by   : map()                         */
  543. /*  Calls       : sqr()                         */
  544. /************************************************************************/
  545.  
  546. static int nearest_color(r, g, b)
  547. unsigned char r, g, b;
  548. {
  549.   int i, near; 
  550.   long int min, error;
  551.   long int sqr();
  552.  
  553.   min = sqr(r-new_pal[0]) + sqr(g-new_pal[1]) + sqr(b-new_pal[2]);
  554.   near = 0;
  555.   for (i=1; i<PALSIZE; i++)
  556.   {
  557.     error = sqr(r-new_pal[3*i]) + sqr(g-new_pal[3*i+1]) + 
  558.         sqr(b-new_pal[3*i+2]);
  559.     if (error < min)
  560.     {
  561.     min = error;
  562.         near = i;
  563.     }
  564.   }
  565.  
  566.   return near;
  567. } /* end of nearest_color */
  568.  
  569.  
  570.  
  571.  
  572. /************************************************************************/
  573. /*  Function    : sqr                           */
  574. /*  Purpose : Computes the square of an integer         */
  575. /*  Parameter   :                           */
  576. /*    x      - an integer                       */
  577. /*  Returns     : The square of x                   */
  578. /*  Called by   : nearest_color()                   */
  579. /*  Calls       : none                          */
  580. /************************************************************************/
  581.  
  582. static long int sqr(x)
  583. unsigned char x;
  584. {
  585.   return (x*x);
  586. }
  587.  
  588.  
  589.  
  590.  
  591.  
  592. /************************************************************************/
  593. /*  Function    : DFCunimcomp                       */
  594. /*  Purpose : 'Decompresses' the compressed image           */
  595. /*  Parameter   :                           */
  596. /*    xdim, ydim - dimensions of image                  */
  597. /*    in, out    - Input buffer and output buffer. Size of input buffer */
  598. /*         is (xdim*ydim)/4. Size of output buffer is 4 times   */
  599. /*         that. It 'restores' images into seq-type files       */
  600. /*  Returns     : none                          */
  601. /*  Called by   : External routines                 */
  602. /*  Calls       : none                          */
  603. /************************************************************************/
  604.  
  605. void DFCunimcomp(xdim, ydim, in, out)
  606. int32 xdim, ydim;
  607. char in[], out[];
  608. {
  609.   int bitmap, temp;
  610.   int i, j, k, x, y;
  611.   unsigned char hi_color, lo_color;
  612.  
  613.   for (y=0; y<(ydim/4); y++)
  614.     for (x=0; x<xdim; x=x+4)
  615.     {
  616.       k = y*xdim + x;
  617.       hi_color = (unsigned char) in[k+2]; 
  618.       lo_color = (unsigned char) in[k+3];
  619.  
  620.       bitmap = ((unsigned char)in[k] << 8) | (unsigned char)in[k+1];
  621.  
  622.       for (i=(y*4); i<(y*4+4); i++)
  623.       {
  624.         temp = bitmap >> (3 + y*4 - i)*4;
  625.         for (j=x; j<(x+4); j++)
  626.         {
  627.       if ((temp & 8) == 8)
  628.         out[i*xdim+j] = (char) hi_color;
  629.       else
  630.         out[i*xdim+j] = (char) lo_color;
  631.       temp = temp << 1;
  632.     }
  633.       }
  634.     } /* end of for x */
  635. } /* end of DFCunimcomp */
  636.  
  637.  
  638.  
  639. /************************************************************************/
  640. /*  Module Name : color                         */
  641. /*  Exports     : sel_palette(); new_pal, pointer to a new color palette*/
  642. /*  Purpose     : Quantizes colors                  */
  643. /*  Author  : Eng-Kiat Koh                      */
  644. /*  Date    : June 30th, 1988                   */
  645. /*  Functions   : sel_palette(), init(), sort(), partition(), find_box()*/
  646. /*        split_box(), assign_color(), select_dim(), find_med() */
  647. /*                classify(), next_pt()                                 */
  648. /************************************************************************/
  649.  
  650.  
  651.  
  652.  
  653.  
  654.  
  655.  
  656. /************************************************************************/
  657. /*  Function    : sel_palette                       */
  658. /*  Purpose : Selects PALSIZE palette colors out of a list of colors*/
  659. /*        in color_pt                       */
  660. /*  Parameter   :                           */
  661. /*    blocks     - number of pixel blocks               */
  662. /*    distinct   - number of distinct colors                */
  663. /*    color_pt   - contains the lo hi colors for each pixel block       */
  664. /*  Returns     : none                          */
  665. /*  Called by   : DFCimcomp()                       */
  666. /*  Calls       : init(), split_box(), find_box(), assign_color()   */
  667. /************************************************************************/
  668.  
  669. static void sel_palette(blocks,distinct, color_pt)
  670. int blocks, distinct;
  671. struct rgb *color_pt;
  672. {
  673.   int boxes;
  674. /*  int i, j;*/
  675.   struct box *ptr;
  676.   struct box *find_box();
  677.   void init();
  678.   void split_box();
  679.   void assign_color();
  680.  
  681.   init(blocks, distinct, color_pt);
  682.  
  683.   /* split box into smaller boxes with about equal number of points */
  684.   for (boxes=1; boxes < PALSIZE; boxes++)
  685.   {
  686. /*
  687.     ptr=frontier->right;
  688.     j = 0;
  689.     while (ptr != NULL)
  690.     {
  691.       printf("Box %d, distinct %d, total %d\n",j,ptr->nmbr_distinct,
  692.              ptr->nmbr_pts);
  693.       for (i=0; i<ptr->nmbr_distinct; i++)
  694.         printf("pt %d: %d %d %d",i,distinct_pt[ptr->pts[i]].c[RED],
  695.                 distinct_pt[ptr->pts[i]].c[GREEN], 
  696.             distinct_pt[ptr->pts[i]].c[BLUE]);
  697.       j++;
  698.       ptr = ptr->right;
  699.     }
  700. */
  701.  
  702.     ptr = find_box();
  703.     split_box(ptr);
  704.   } 
  705.  
  706.   assign_color();
  707. }
  708.  
  709.  
  710.  
  711.  
  712.  
  713.  
  714. /************************************************************************/
  715. /*  Function    : init                          */
  716. /*  Purpose : Initializes the global variables, sets up the first   */
  717. /*        box. It will contain all the color points     */
  718. /*  Parameter   :                           */
  719. /*    blocks     - number of pixel blocks               */
  720. /*    distinct   - number of distinct colors                */
  721. /*    color_pt   - contains the lo hi colors for each pixel block       */
  722. /*  Returns     : none                          */
  723. /*  Called by   : sel_palette()                     */
  724. /*  Calls       : none                          */
  725. /************************************************************************/
  726.  
  727. static void init(blocks, distinct, color_pt)
  728. int blocks, distinct;
  729. struct rgb *color_pt;
  730. {
  731.   int i, j, k, l;
  732.   int temp[MAXCOLOR];
  733.   struct box *first;
  734.   struct box *dummy;
  735.  
  736.   /* alloc memory */
  737.   if (hist) DFIfreespace((char *) hist);
  738.   if (distinct_pt) DFIfreespace((char*) distinct_pt);
  739.   hist = (int *)DFIgetspace((unsigned)distinct * sizeof(int));
  740.   distinct_pt = (struct rgb *)DFIgetspace((unsigned)distinct *
  741.                       sizeof(struct rgb));
  742.  
  743.   for (i=0; i<distinct; i++)
  744.     hist[i] = 0;
  745.  
  746.  
  747.   /* select distinct pts and set up histogram */
  748.   for (i=0; i<MAXCOLOR; i++)
  749.     temp[i] = -1;
  750.  
  751.   k = 0;
  752.   for (i=0; i<(2*blocks); i++)
  753.   {
  754.     j = (color_pt[i].c[RED] << 10) | (color_pt[i].c[GREEN] << 5) |
  755.         color_pt[i].c[BLUE];
  756.  
  757.     if (temp[j] == -1)
  758.     {
  759.       /* new pt */
  760.       temp[j] = k;
  761.       for (l=RED; l<=BLUE; l++)
  762.     distinct_pt[k].c[l] = color_pt[i].c[l];
  763.       k++;
  764.    }
  765.  
  766.    hist[temp[j]]++;
  767.   }
  768.  
  769.       
  770.   /* set up first box */
  771.   first = (struct box *)DFIgetspace(sizeof(struct box));
  772.   for (i=RED; i<=BLUE; i++)
  773.   {
  774.     first->bnd[i][LO] = 999.9;
  775.     first->bnd[i][HI] = -999.9;
  776.  
  777.     for (j=0; j<distinct; j++)
  778.     {
  779.       if (first->bnd[i][LO] > (float)distinct_pt[j].c[i])
  780.     first->bnd[i][LO] = (float)distinct_pt[j].c[i];
  781.  
  782.       if (first->bnd[i][HI] < (float)distinct_pt[j].c[i])
  783.     first->bnd[i][HI] = (float)distinct_pt[j].c[i];
  784.     } /* end of for j */
  785.  
  786.     first->bnd[i][LO] = first->bnd[i][LO] - EPSILON;
  787.     first->bnd[i][HI] = first->bnd[i][HI] + EPSILON;
  788.   } /* end of for i */
  789.  
  790.   first->pts = (int *)DFIgetspace((unsigned)distinct * sizeof(int));
  791.   for (i=0; i<distinct; i++)
  792.     first->pts[i] = i;
  793.   first->nmbr_pts = 2*blocks;
  794.   first->nmbr_distinct = distinct;
  795.  
  796.   dummy = (struct box *)DFIgetspace(sizeof(struct box));
  797.   frontier = dummy;
  798.   dummy->right = first;
  799.   first->left = dummy;
  800.   first->right = NULL;
  801.   dummy->nmbr_pts = 0;
  802.  
  803.   DFIfreespace((char *)first);
  804.   DFIfreespace((char *)dummy);
  805. } /* end of init */
  806.  
  807.  
  808.  
  809.  
  810.  
  811.  
  812.  
  813. /************************************************************************/
  814. /*  Function    : sort                          */
  815. /*  Purpose : Performs quick sort on the points in a box along a    */
  816. /*        given dimension                   */
  817. /*  Parameter   :                           */
  818. /*    l, r   - index of leftmost and rightmost element      */
  819. /*    dim    - dimension along which sorting is done        */
  820. /*    rank   - an array which carries the index of the points to be */
  821. /*         sorted                       */
  822. /*  Returns     : none                          */
  823. /*  Called by   : find_med()                        */
  824. /*  Calls       : partition()                       */
  825. /************************************************************************/
  826.  
  827. static void sort(l,r,dim, rank)
  828. int l, r, dim, rank[];
  829. {
  830.   int i;
  831.   int partition();
  832.   void sort();
  833.  
  834.   if (r > l)
  835.   {
  836.     i = partition(l, r, dim, rank);
  837.     sort(l, i-1, dim, rank);
  838.     sort(i+1, r, dim, rank);
  839.   }
  840. }
  841.  
  842.  
  843.  
  844.  
  845.  
  846.  
  847. /************************************************************************/
  848. /*  Function    : partition                     */
  849. /*  Purpose : Partitions the list into 2 parts as in the quick sort */
  850. /*        algorithm                     */
  851. /*  Parameter   :                           */
  852. /*    l, r   - index of leftmost and rightmost element      */
  853. /*    dim    - dimension along which sorting is done        */
  854. /*    rank   - an array which carries the index of the points to be */
  855. /*  Returns     : index where list is partitioned           */
  856. /*  Called by   : sort()                        */
  857. /*  Calls       : none                          */
  858. /************************************************************************/
  859.  
  860. static int partition(l, r, dim, rank)
  861. int l, r, dim, rank[];
  862. {
  863.   int i, j, temp;
  864.   char v;
  865.   
  866.   v = distinct_pt[rank[r]].c[dim];
  867.   i = l-1;
  868.   j = r;
  869.  
  870.   /* repeat until i and j crosses */
  871.   do
  872.   {
  873.     /* repeat until an element >= v is found */
  874.     do
  875.       i++;
  876.     while (distinct_pt[rank[i]].c[dim] < v);
  877.  
  878.     /* repeat until an element <= v is found */
  879.     do
  880.       j--;
  881.     while ((j>0) && (distinct_pt[rank[j]].c[dim] > v));
  882.  
  883.     /* swap pointers */
  884.     temp = rank[i];
  885.     rank[i] = rank[j];
  886.     rank[j] = temp;
  887.   }
  888.   while (i < j);
  889.  
  890.   /* position partitioning element at location i */
  891.   temp = rank[j];
  892.   rank[j] = rank[i];
  893.   rank[i] = rank[r];
  894.   rank[r] = temp;
  895.  
  896.   return i;
  897. }
  898.  
  899.  
  900.  
  901.  
  902.  
  903. /************************************************************************/
  904. /*  Function    : find_box                      */
  905. /*  Purpose : Finds the box with the largest number of color points */
  906. /*        The points need not necessarily be distinct. But in   */
  907. /*        order to partition the box, there must be at least  2 */
  908. /*        distinct points                   */
  909. /*  Parameter   : none                          */
  910. /*  Returns     : pointer to box selected for splitting         */
  911. /*  Called by   : sel_palette()                     */
  912. /*  Calls       : none                          */
  913. /************************************************************************/
  914.  
  915. static struct box *find_box()
  916. {
  917.   struct box *temp;
  918.   struct box *max;
  919.   int max_pts;
  920.  
  921.   max_pts = 1;
  922.   max = NULL;
  923.   temp = frontier->right;
  924.   while (temp != NULL)
  925.     if ((temp->nmbr_distinct > 1) && (max_pts < temp->nmbr_pts))
  926.     {
  927.       max_pts = temp->nmbr_pts;
  928.       max = temp;
  929.       temp = temp->right;
  930.     }
  931.     else
  932.       temp = temp->right;
  933.  
  934.   if (max == NULL)
  935.   {
  936.     printf("Error : Number of color points < palette \n");
  937.     exit(1);
  938.   }
  939.  
  940.   return max;
  941. }
  942.  
  943.  
  944.  
  945.  
  946.  
  947. /************************************************************************/
  948. /*  Function    : split_box                     */
  949. /*  Purpose : Splits a selected box into 2 and reinserts the 2 sub- */
  950. /*        boxes into the frontier list              */
  951. /*  Parameter   :                           */
  952. /*    ptr    - pointer to box to be split               */
  953. /*  Returns     : none                          */
  954. /*  Called by   : sel_palette()                     */
  955. /*  Calls       : find_med(), select_dim(), classify()          */
  956. /************************************************************************/
  957.  
  958. static void split_box(ptr)
  959. struct box *ptr;
  960. {
  961.   int dim, j, i;
  962.   float median;
  963.   struct box *l_child, *r_child;
  964.   int select_dim();
  965.   float find_med();
  966.   void classify();
  967.   
  968.   dim = select_dim(ptr);
  969.   median = find_med(ptr, dim);
  970.  
  971.   /* create 2 child */
  972.   l_child = (struct box *)DFIgetspace(sizeof(struct box));
  973.   r_child = (struct box *)DFIgetspace(sizeof(struct box));
  974.   
  975.   for (i=RED; i<=BLUE; i++)
  976.     for (j=HI; j<=LO; j++)
  977.     {
  978.       l_child->bnd[i][j] = ptr->bnd[i][j];
  979.       r_child->bnd[i][j] = ptr->bnd[i][j];
  980.     }
  981.   l_child->bnd[dim][HI] = median;
  982.   r_child->bnd[dim][LO] = median;
  983.  
  984.   classify(ptr,l_child);
  985.   classify(ptr,r_child);
  986.  
  987.   r_child->right = ptr->right;
  988.   r_child->left = l_child;
  989.   l_child->right = r_child;
  990.   l_child->left = ptr->left;
  991.   (ptr->left)->right = l_child;
  992.   if (ptr->right != NULL)
  993.     (ptr->right)->left = r_child;
  994. } /* end of split_box */
  995.  
  996.  
  997.  
  998.  
  999.  
  1000.  
  1001. /************************************************************************/
  1002. /*  Function    : assign_color                      */
  1003. /*  Purpose : Assigns a color to each box. It computes the average  */
  1004. /*        color of all the points in the box            */
  1005. /*        Sets up the new_pal buffer. Each color component is   */
  1006. /*        shifted left 3 bits because of the truncation when    */
  1007. /*        color_pt was set up                   */
  1008. /*  Parameter   : none                          */
  1009. /*  Returns     : none                          */
  1010. /*  Called by   : sel_palette()                     */
  1011. /*  Calls       : none                          */
  1012. /************************************************************************/
  1013.  
  1014.  
  1015. static void assign_color()
  1016. {
  1017.   struct box *temp;
  1018.   int ent, k, j;
  1019.   int c[3];
  1020.  
  1021.   temp = frontier->right;
  1022.   for (ent=0; ent<PALSIZE; ent++)
  1023.   {
  1024.     for (k=RED; k<=BLUE; k++)
  1025.       c[k] = 0;
  1026.  
  1027. /*
  1028.     printf("Box %d: number of pts %d\n", ent, temp->nmbr_pts);
  1029. */
  1030.  
  1031.     for (j=0; j<temp->nmbr_distinct; j++)
  1032.     {
  1033. /*
  1034.       printf("pt %d:", j);
  1035. */
  1036.       for (k=RED; k<=BLUE; k++)
  1037.       {
  1038. /*
  1039.         printf("%d ",distinct_pt[temp->pts[j]].c[k]);
  1040. */
  1041.     c[k] = c[k] + distinct_pt[temp->pts[j]].c[k]*hist[temp->pts[j]];
  1042.       }
  1043. /*
  1044.       printf("\n");
  1045. */
  1046.     }
  1047.  
  1048.     for (k=RED; k<=BLUE; k++)
  1049.     {
  1050.       c[k] = c[k] / temp->nmbr_pts;
  1051.       new_pal[3*ent+k] = c[k] << 3;
  1052.     }
  1053.     
  1054.     temp = temp->right;
  1055.   } /* end of for entry */
  1056. }
  1057.  
  1058.  
  1059.  
  1060.  
  1061.  
  1062. /************************************************************************/
  1063. /*  Function    : select_dim                        */
  1064. /*  Purpose : Selects the dimension with the largest spread         */
  1065. /*  Parameter   :                           */
  1066. /*    ptr    - pointer to desired box               */
  1067. /*  Returns     : dimension where the box is to be split        */
  1068. /*  Called by   : split_box()                       */
  1069. /*  Calls       : none                          */
  1070. /************************************************************************/
  1071.  
  1072. static int select_dim(ptr)
  1073. struct box *ptr;
  1074. {
  1075.   int i, j, low[3], high[3];
  1076.   int max;
  1077.  
  1078.  
  1079.   for (j=RED; j<=BLUE; j++)
  1080.   {
  1081.     low[j] = distinct_pt[ptr->pts[0]].c[j];
  1082.     high[j] = distinct_pt[ptr->pts[0]].c[j];
  1083.   }
  1084.  
  1085.   for (i=1; i<ptr->nmbr_distinct; i++)
  1086.     for (j=RED; j<=BLUE; j++)
  1087.     {
  1088.       if (low[j] > distinct_pt[ptr->pts[i]].c[j])
  1089.     low[j] = distinct_pt[ptr->pts[i]].c[j];
  1090.       if (high[j] < distinct_pt[ptr->pts[i]].c[j])
  1091.     high[j] = distinct_pt[ptr->pts[i]].c[j];
  1092.     }
  1093.  
  1094.   max = high[RED] - low[RED];
  1095.   i = RED;
  1096.   for (j=GREEN; j<=BLUE; j++)
  1097.     if (max < (high[j] - low[j]))
  1098.     {
  1099.       max = high[j] - low[j];
  1100.       i = j;
  1101.     }
  1102.  
  1103.   return i;
  1104. } /* end of select_dim */
  1105.  
  1106.  
  1107.  
  1108.  
  1109.  
  1110. /************************************************************************/
  1111. /*  Function    : find_med                      */
  1112. /*  Purpose : Finds the point where the box is to be split. It finds*/
  1113. /*        a point such that the 2 new boxes have about the same */
  1114. /*        number of color points.               */
  1115. /*  Parameter   :                           */
  1116. /*    ptr    - pointer to box to be split               */
  1117. /*    dim    - dimension to split box               */
  1118. /*  Returns     : point where the box is to be cut          */
  1119. /*  Called by   : split_box()                       */
  1120. /*  Calls       : next_pt()                     */
  1121. /************************************************************************/
  1122.  
  1123. static float find_med(ptr,dim)
  1124. struct box *ptr;
  1125. int dim;
  1126. {
  1127.   int i, j, count, next, prev;
  1128.   int *rank;
  1129.   float median;
  1130.   int next_pt();
  1131.   void sort();
  1132.  
  1133.   rank = (int *)DFIgetspace((unsigned)ptr->nmbr_distinct * sizeof(int));
  1134.   for (i=0; i<ptr->nmbr_distinct; i++)
  1135.     rank[i] = ptr->pts[i];
  1136.  
  1137.   sort(0,ptr->nmbr_distinct-1,dim,rank);
  1138. /*
  1139.   for (i=0; i<ptr->nmbr_distinct; i++)
  1140.     printf("find_med: sorted list is %d\n",distinct_pt[rank[i]].c[dim]);
  1141. */
  1142.   
  1143.  
  1144.   count = 0;
  1145.   i = 0;
  1146.   while ((i < ptr->nmbr_distinct) && (count < ptr->nmbr_pts/2))
  1147.   {
  1148.     next = next_pt(dim, i, rank, ptr->nmbr_distinct);
  1149.     for (j=i; j<next; j++)
  1150.       count = count + hist[rank[j]];
  1151.  
  1152.     prev = i;
  1153.     i = next; 
  1154.   }
  1155.  
  1156.   if (prev == 0)
  1157.   {
  1158.     /* the first distinct point overshot the median */
  1159.     median = (float)distinct_pt[rank[prev]].c[dim] + EPSILON;
  1160.   }
  1161.   else
  1162.     median = (float)distinct_pt[rank[prev-1]].c[dim] + EPSILON;
  1163.    
  1164.   DFIfreespace((char *) rank);
  1165.   return median;
  1166. } /* end of find_med */
  1167.   
  1168.  
  1169.  
  1170.  
  1171.  
  1172.  
  1173. /************************************************************************/
  1174. /*  Function    : classify                      */
  1175. /*  Purpose : Looks at the color points in the parent and selects   */
  1176. /*        the points that belong to the child           */
  1177. /*  Parameter   :                           */
  1178. /*    ptr    - pointer to parent                    */
  1179. /*    child  - pointer to child box                 */
  1180. /*  Returns     : none                          */
  1181. /*  Called by   : split_box()                       */
  1182. /*  Calls       : none                          */
  1183. /************************************************************************/
  1184.  
  1185. static void classify(ptr, child)
  1186. struct box *ptr, *child;
  1187. {
  1188.   int i, j;
  1189.   int *temp;
  1190.   int distinct, total;
  1191.  
  1192.   temp = (int *)DFIgetspace((unsigned)ptr->nmbr_distinct * sizeof(int));
  1193.  
  1194.   distinct = 0;
  1195.   total = 0;
  1196.   for (i=0; i<ptr->nmbr_distinct; i++)
  1197.   {
  1198.     j = ptr->pts[i];
  1199.     if ((((float)distinct_pt[j].c[RED] >= child->bnd[RED][LO]) &&
  1200.          ((float)distinct_pt[j].c[RED] <= child->bnd[RED][HI])) &&
  1201.         (((float)distinct_pt[j].c[GREEN] >= child->bnd[GREEN][LO]) &&
  1202.          ((float)distinct_pt[j].c[GREEN] <= child->bnd[GREEN][HI])) &&
  1203.         (((float)distinct_pt[j].c[BLUE] >= child->bnd[BLUE][LO]) &&
  1204.          ((float)distinct_pt[j].c[BLUE] <= child->bnd[BLUE][HI])))
  1205.     {
  1206.       /* pt is in new box */
  1207.       temp[distinct] = j;
  1208.       distinct++;
  1209.       total = total + hist[j];
  1210.     } /* end of if */
  1211.   } /* end of for i */
  1212.  
  1213.   /* assign points */
  1214.   child->nmbr_pts = total;
  1215.   child->nmbr_distinct = distinct;
  1216.   child->pts = (int *)DFIgetspace((unsigned)distinct * sizeof(int));
  1217.   for (i=0; i<distinct; i++)
  1218.     child->pts[i] = temp[i];
  1219.  
  1220.   DFIfreespace((char *)temp);
  1221.  
  1222. } /* end of classify */
  1223.  
  1224.  
  1225.  
  1226.  
  1227.  
  1228. /************************************************************************/
  1229. /*  Function    : next_pt                       */
  1230. /*  Purpose : Determines the next point that has a different value  */
  1231. /*        from the current point along  a dimension     */
  1232. /*  Parameter   :                           */
  1233. /*    dim    - dimension where box is to be split           */
  1234. /*    i      - index to current point               */
  1235. /*    rank       - sorted list of points to be searched starting from i */
  1236. /*    distinct   - length of sorted list                                */
  1237. /*  Returns     : index of point that has a different value     */
  1238. /*  Called by   : find_med                      */
  1239. /*  Calls       : none                          */
  1240. /************************************************************************/
  1241.  
  1242. static int next_pt(dim, i, rank, distinct)
  1243. int dim, i, rank[], distinct;
  1244. {
  1245.   int j;
  1246.   char old;
  1247.  
  1248.   old = distinct_pt[rank[i]].c[dim];
  1249.   for (j=(i+1); j<distinct; j++)
  1250.     if (distinct_pt[rank[j]].c[dim] != old)
  1251.       break;
  1252.  
  1253.   return j;
  1254. } /* end of next_pt */
  1255.  
  1256.